package everyday.leetcode;

import java.util.Arrays;

/**
 * @Author: wenjingyuan
 * @Date: 2022/10/08/15:46
 * @Description:870优势洗牌
 * https://leetcode.cn/problems/advantage-shuffle/
 */
public class Num870 {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        //类比田忌赛马，数组中最小值即下等马，最大值上等马
        //每次用nums1中的下等马去跟nums2中的下等马pk
        //如果干的过就干，干不过就用nums1中的下等马去当炮灰，去干nums2中的上等马
        //在本题中，如果干的过，就用nums2中的下等马的下标当做nums1中的下等马的下标
        //干不过，就用nums2中的上等马的下标当作nums1中的下等马的下标
        Arrays.sort(nums1);
        int len=nums2.length;
        Integer[] index=new Integer[len];
        int[] res=new int[len];
        for(int i=0 ; i < len ; i++ ){
            index[i]=i;
        }
        //注意比较器引用的数组需要是对象，所以不能放基本数据类型的数组
        //根据nums2的值升序，来排序nums2的值的对应下标
        //排序后index[]中第一个元素是nums2中最小值的下标，第二个元素是nums2中第二小值的下标
        Arrays.sort(index,(a,b)->(nums2[a]-nums2[b]));
        int left=0;
        int right=len-1;
        //遍历nums1
        for(int num:nums1){
            //index[left] 为 nums2中最小值的下标，index[right] 为nums2中最大值的下标
            //如果num比nums2中的最小值大，则本次res中num对应的下标为index[left],然后left++
            //否则本次res中num对应的下标为index[right],然后right--
            int i=num>nums2[index[left]]? index[left++]:index[right--];
            res[i]=num;
        }
        return  res;
    }
}
